package com.liwenfeng.linkedlist;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Function;

public class MyLinkedList<E> {
    Node<E> head = null;
    private int size = 0;
    ArrayList<E> es = new ArrayList<>();

    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public boolean add(E e) {
        if (head == null) {
            head = new Node<E>(e, null);
            size++;
        } else {
            //在尾结点插入，先找尾结点
            Node<E> temp = head;
            //让temp走到尾结点
            while (temp.next != null) {
                temp = temp.next;
            }
            //next为null，temp是尾结点，创建新结点，加入temp.next
            temp.next = new Node<>(e, null);
            size++;
        }
        return true;
    }

    public int size() {
        return size;
    }

    public void forEach(Consumer<E> consumer) {
        if (head == null) return;
        Node<E> temp = head;
        while (temp != null) {
            consumer.accept(temp.data);
            temp = temp.next;
        }
    }

    public void sort(Comparator<E> comparator) {
        es.clear();
        forEach(es::add);
        es.sort(comparator);
        head = null;
        size = 0;
        es.forEach(this::add);
    }

    public <U extends Comparable<U>> void sort(Function<E, U> keyExtractor, Sortord sortord) {
        es.clear();
        forEach(es::add);
        switch (sortord) {
            case FAST -> fastSort(es, 0, es.size() - 1, keyExtractor);
            case BUBBLE -> bubbleSort(keyExtractor);
            case INSERT -> insertSort(keyExtractor);
        }
        head = null;
        size = 0;
        es.forEach(this::add);
    }

    public <U extends Comparable<U>> void sort(Function<E, U> keyExtractor) {
        sort(keyExtractor, Sortord.FAST);
    }

    //合并两个链表，keyExtractor是提取器，从E对象中提取可比较类型，asc默认为升序，false为降序
    public <U extends Comparable<U>> void mergeSort(MyLinkedList<E> list, Function<E, U> keyExtractor, boolean isAsc) {
        list.forEach(this::add);
        sort((o1, o2) -> isAsc ? keyExtractor.apply(o1).compareTo(keyExtractor.apply(o2)) : keyExtractor.apply(o2).compareTo(keyExtractor.apply(o1)));
    }

    public <U extends Comparable<U>> void mergeSort(MyLinkedList<E> list, boolean asc) {
        mergeSort(list, e -> (U) e, asc);
    }

    public <U extends Comparable<U>> void mergeSort(MyLinkedList<E> list) {
        mergeSort(list, e -> (U) e, true);
    }

    public void merge(MyLinkedList<E> list) {
        list.forEach(this::add);
    }

    //删除链表元素
    public boolean remove(E data) {
        Node<E> temp, temp1;
        temp = temp1 = head;
        while (temp != null) {
            if (temp.data == data) {
                if (temp == head) {
                    head = temp.next;
                } else {
                    temp1.next = temp.next;
                }
                size--;
                return true;
            }
            temp1 = temp;
            temp = temp.next;
        }
        return false;
    }

    //快速排序法
    public <U extends Comparable<U>> void fastSort(List<E> es, int start, int end, Function<E, U> keyExtractor) {
        if (end > start) {
            E pivot = es.get(start);
            int left = start, right = end;
            while (right > left) {
                if (keyExtractor.apply(es.get(right)).compareTo(keyExtractor.apply(pivot)) < 0) {
                    es.set(left, es.get(right));
                    left++;
                } else {
                    right--;
                    continue;
                }
                while (right > left) {
                    if (keyExtractor.apply(es.get(left)).compareTo(keyExtractor.apply(pivot)) > 0) {
                        es.set(right, es.get(left));
                        right--;
                        break;
                    } else {
                        left++;
                    }
                }
            }
            es.set(left, pivot);

            fastSort(es, start, left - 1, keyExtractor);
            fastSort(es, left + 1, end, keyExtractor);
        }
    }

    //冒泡排序法
    public <U extends Comparable<U>> void bubbleSort(Function<E, U> keyExtractor) {
        for (int j = es.size() - 1; j > 0; j--) {
            for (int i = 0; i < j; i++) {
                if (keyExtractor.apply(es.get(i)).compareTo(keyExtractor.apply(es.get(i + 1))) > 0) {
                    E temp = es.get(i);
                    es.set(i, es.get(i + 1));
                    es.set(i + 1, temp);
                }
            }
        }
    }

    //插入排序法
    public <U extends Comparable<U>> void insertSort(Function<E, U> keyExtractor) {
        //记录开始无序的位置索引
        int startIndex = -1;
        for (int i = 0; i < es.size(); i++) {
            if (keyExtractor.apply(es.get(i)).compareTo(keyExtractor.apply(es.get(i + 1))) > 0) {
                startIndex = i + 1;
                break;
            }
        }

        //遍历从startIndex开始到最后一个元素，依次插入有序部分
        for (int i = startIndex; i < es.size(); i++) {
            int j = i;
            while (j > 0 && keyExtractor.apply(es.get(j)).compareTo(keyExtractor.apply(es.get(j - 1))) < 0) {
                E temp = es.get(j);
                es.set(j, es.get(j - 1));
                es.set(j - 1, temp);
                j--;
            }
        }
    }

    public void reversed() {
        es.clear();
        forEach(e -> es.add(0, e));
        head = null;
        size = 0;
        es.forEach(this::add);
    }

    //迭代器
    class Itr {
        private int cursor = 0;
        private int lastRet = -1;
        private Node<E> previous = null;
        private Node<E> current = null;

        public boolean hasNext() {
            return cursor != size;
        }

        public E next() {
            Node<E> next;
            if (cursor == 0) {
                next = current=head;
            } else {
                next = current.next;
                previous = current;
                current = current.next;
            }
            lastRet = cursor++;
            return next.data;
        }

        public boolean hasCurrent() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int currentIndex() {
            return cursor - 1;
        }

        public E current() {
            if (current == null) return null;
            return current.data;
        }

        public void set(E e) {
            if (current == null) {
                head = previous = current = new Node<E>(e, null);
                size++;
                this.next();
            }else {
                current.data = e;
            }
        }

        public void add(E e) {
            if (head == null) {
                head= previous = current = new Node<E>(e, null);
            } else {
                if (cursor==0){
                    head= new Node<E>(e, head);
                }else {
                    current.next = new Node<E>(e, current.next);
                }
            }
            size++;
        }

        public void remove() {
            if (lastRet < 0) return;
            if (current == head) {
                head = current.next;
                previous = current = head;
            } else {
                previous.next = current.next;
            }
            cursor--;
            lastRet = cursor - 1;
            size--;
        }
    }

    public Itr iterator() {
        return new Itr();
    }

    public E get(int index) {
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
        Node<E> temp = head;

        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp.data;

        //迭代器方法
//        Itr it = iterator();
//        while (it.hasNext()) {
//            E next = it.next();
//            if (it.lastRet == index) {
//                return next;
//            }
//        }
//        return null;
    }

    enum Sortord {
        BUBBLE, INSERT, FAST;
    }
}
